#include "gx_bsearch.h"
#include <stdio.h>


void* bsearch(void* key,void* base,unsigned n,unsigned itemsize,int(*compare)(const void*,const void*))
{
	if(!base||n==0||key == NULL || compare== NULL)
		return NULL;
	char* array = (char*)base;

	if(compare(key,array+(n-1)*itemsize) > 0)
		return NULL;

	if(compare(key,array) < 0)
		return NULL;

	if(compare(key,array+(n-1)*itemsize) == 0)
		return array+(n-1)*itemsize;

	if(compare(key,array) == 0)
		return array;

	unsigned m = (n+1)/2;

	if(compare(array+m*itemsize,key) == 0)
		return array+m*itemsize;
	else if(compare(array+m*itemsize,key) < 0)
		return bsearch(key,(void*)(array+(m+1)*itemsize),n-(m+1),itemsize,compare);
	else
		return bsearch(key,(void*)array,m,itemsize,compare);
}

/*
int* bsearch(int key,int array[],unsigned n)
{
	if (!array || n == 0)
		return NULL;

	if(key > array[n-1])
		return NULL;
	
	if(key < array[0])
		return NULL;

	if(key == array[n-1])
		return array+n-1;

	if(key == array[0])
		return array;

	unsigned m = (n+1)/2;

	if(array[m] == key)
		return array+m;
	else if(array[m] < key)
		return bsearch(key,array+m+1,n-(m+1));
	else 
		return bsearch(key,array,m);
}
*/
